\documentclass{aamas2012}
 
\pdfpagewidth=8.5truein
\pdfpageheight=11truein

\begin{document}
\title{Wa-Tor world : a Multiagent Predator-Prey Simulation}

\numberofauthors{3}

\author{
	\alignauthor 
	Alioune Schurz\\
	\email{alioune.schurz@gmail.com}		
	\alignauthor 
	Barbara Sepic\\
	\email{barbara.sepic@gmail.com}
	\alignauthor 
	Felix Stahlberg\\
	\email{fstahlberg@gmail.com}
}

\maketitle

\begin{abstract}
Here comes the abstract.
\end{abstract}

\keywords{Wa-Tor, Multi-Agents, Predator and Prey}

\section{Introduction}
The evolution theory is a widly accepted fact in the scientific community and confirmed by numerous experiments in the field of biological science. But evolution is not only restricted to the physical abilities of individuals, but also can be extended to behaviors which proved to be beneficial for a species. A common behavioral phenomenon observable in our nature is the building of large flocks and schools, especially for species aiming to protect themeself against predators. Apparently, flocks are beneficial 

% --------------------------
\section{Related work}
Prey-predator simulation is very well know problem in big system simulation and there are
numerous different approaches to this kind of problems.
Some use mathematical equations to model groups of agents whereas some model
every agent individually and then study the global outcome.
Prey-predator simulation can be seen as a subset of social modeling. For instance techniques used in \cite{criminals},
to model Guardians, Criminals and Passer-by in the context of crime-prevention may be used for Prey-predator 
modeling as well. Therefore a lot of studies in the area of social modeling can be seen as related work. 
\\Yet our study mostly stems from ideas developped in \cite{wator}. In this paper, the 
author describes its ``Computer recreations'' that led him create an ecosystem modeled as a cellular automaton.
This ecosystem takes place on the planet Wa-Tor, completely covered by water, in which co-exists only 2 species:
fishes and sharks. The planet is toroidal, meaning that if a living creature moves down passed the bottom of the world, 
it would reappear at the upper edge. Similarly by rotation and symetry, the same rules apply for the top, left and right 
edges. Both sharks and fish live, move, reproduce and die in Wa-Tor, according to the a certain number of rules. Time passes in discrete 
steps called "chronons". In this paper, we study different strategies for both species. The most sophisticated strategy we tried uses ideas from \cite{flocks:herds} in order to implement flocking, predator avoidance, and prey attraction.

% --------------------------
\section{Experimental setup}
The goal of our study is to evaluate different movement startegies for both predators and preys
and the effect of different species' parameters on the overall population.

In this section we first describe the Wa-tor world and its rules, then discuss our implementation.
\subsection{The Wa-Tor world}
The simulation environment we used in this paper is very close to the Wa-tor world described in \cite{wator}.
Still, it contains some differences regarding the number of species available and their strategies. 
The topology, only available in 2D in the later paper, becomes available in 3D for our implementation. In this section we describe our simulation world and the rules that apply to the agents living in it. Please note that we reuse the name Wa-Tor for our simulation world although it slightly differs from the original one.

\subsubsection{Simulation overview}
A simulation consists of rounds. A round can be seen as a discret unit of time. It is comparable to the ``chronon'' in \cite{wator}.
Between two rounds, all the agents living in the world will have to make a decision regarding to the spatial position they wish to
occupy next. Each agent might take into account the agents close to it in the decision process. 

\subsubsection{Common rules for all agents}
The following rules apply to individuals of all species in the Wa-Tor world:
\begin{itemize}
 \item An agent can only see other agents if and only if they are whithin the so called \textbf{neighborhood radius}. In other words, during the movement decision process, an agent can only take into account agents in its neighborhood. The neighborhood radius is a global constant valid for all species.
 \item All agents have a \textbf{breed time}. The breed time is the number of rounds after which the agent will reproduce. In our simulation, reproduction requires only one parent. As a consequence, if the world only contains one agent, it will still be able to reproduce. The breed time could therefore also be called duplication time.
\end{itemize}

\subsubsection{Specific rules for predators}
The following rule applies to all predators in the Wa-Tor world:
\begin{itemize}
 \item All predators of the same species have a \textbf{starve time}. It represents the time a predator can survive without eating. After the starve time is exceeded, the agent dies and is removed from the Wa-Tor world.
\end{itemize}

\subsubsection{Possible simulation outcomes}
\label{subsubsec:outcomes}
The balance of this ecosystem is very delicate: the population size of the species can follow signifcantly different cycles depending on the starve time and breed time, as well as starting positions of each agent.
We may go from both species being endangered to an abundance of one or both. In a way, Wa-Tor simulates what really can be observed in nature, showing the evolution of the population of a species and its natural predator, 
and the mutual dependencies between them. When the prey are numerous, predators can reproduce rapidly.
However, more predators increase the number of prey ate and the population of the prey decreases. With rarer prey, predators begin to starve and die of starvation, decreasing their population and easing the pressure on hunting prey. The prey can then go back to rapidly reproducing as the cycle repeats itself.

We run simulations for a predefined \textit{maximum number of rounds} (units of time) and count the population of each species afterwards. The possible outcomes are: 
\begin{enumerate}
\item \textbf{Equilibrium} : After the \textit{maximum number of rounds} both predator and preys remain.
\item \textbf{Preys win} : After the \textit{maximum number of rounds}, only prey remains.
\item \textbf{Predators win} : After the \textit{maximum number of rounds}, neither preys nor predators remain or only predators remain. Please note, that the first one can be considered only as a partial victory since predator have no interest in seeing the preys' population eradicated. Soon after, the former case would appear, because the predators would die by starvation.
\end{enumerate}

To estimate the effect of different parameters on simulations, we set the \textit{maximum number of rounds} high and compute an overall outcome over several simulations. Our implemented rules used to derive a global outcome out of multiple simulation are described below:

\begin{enumerate}
 \item We count the number of outcomes 1,2 and 3 and compute their frequencies.
 \item In order to output outcome 2 or 3, the number of occurences of this outcome has to be the majority among all outcomes. For instance, if 4, 6, 10
is the number of respectively outcome 1, 2 and 3, then the overall outcome will be 3. Indeed, the
frequencies of the different outcome are 20\%, 30\%, 50\% so outcome 3 has the majority.
 \item If neither outcome 2 nor 3 has the majority, we just output outcome 1.
\end{enumerate}

\subsection{Implementation}
Before studying the effect of species' parameters on the different strategies, we had to build
some tools to facilitate the running experiment. Below, we describe the framework used as a
base for our implementation, the graphical user interface.

\subsubsection{The Wa-Tor framework}
We developed a framework for Wa-Tor like prey-predator simulations. This framework provides agent abstraction, population, topology and strategy abstraction using all the rules we have described above. To meet a variety of user requirements, we developed both, a graphical user interface for simulations and strategy's visualisation and a command-line user interface for running the tests and generating diagrams. The framework offers a interface for easily adding new behaviors (see movement strategies in section \ref{sec:strategies}) or species.

\subsubsection{Wa-Tor graphic user interface}
In order to visualize the effects of different parameters and strategies, we implemented a comprehensive GUI. Its main functionalities are:
\begin{itemize}
 \item Select species for the simulation.
 \item Setup the parameters for the species (initial number of individuals, breed and starve time).
 \item Choose the movement strategy for each species and change the strategy parameters.
 \item Choose between a 2D or 3D topology and specify the size of the Wa-Tor world.
 \item Start, stop, reset simulations.
 \item Adjust the simulation speed.
 \item Rotate and move the camera in space for a better overview over the Wa-Tor world.
\end{itemize}

Appendix~\ref{app:GUI} provides few screenshots of our graphical user interface.

\subsubsection{Simulation recorder and viewer}
To be able to plot population-time diagrams\footnote{the population size of one or more species over the number of simulation rounds.} we developed a module to log the simulation. This module records in each round the number of individuals of each species selected for the simulation. The names of the different species are also saved in
the file. The module will automatically follow a simulation initiated through the GUI. Additionally, we developed a python script, 
using $\mathtt{matplotlib}$, designed for plotting the population-time diagrams based on such log files.

\subsubsection{Wa-Tor batch simulation module}
Among diagrams over time, we wish to analyse simulations in the starve and breed-time vector space of the participating species. In this case, the plot shows the distribution of the different outcomes described in Section~\ref{subsubsec:outcomes} as a function of the species' parameters: predator starvation time, predator breed time and prey breed time. Therefore
for each element \[(pred_{starve}, pred_{breed}, prey_{breed})\] in the 3D vector space, we run \textit{numberOfSimulation} simulations and output the overall outcome following rules in Section~\ref{subsubsec:outcomes}. The elements ranges in predefined intervals, set by the user via the command-line interface among other simulation parameters. 

Figure \ref{wator:cli} illustrates the usage for the command-line interface. In this example, $pred_{starve}$, $pred_{breed}$, and $prey_{breed}$ will each be within $[1,10]$ and the iteration step for all the three parameters will be 1. 
The command \texttt{ls} displays the different species and associated information (movement strategy, initial population sizes). The command \texttt{start} launches the simulation and simultainously sets up the intervals for the parameters. The results of the global outcome and the configuration will be saved in an output file.

Finally, we implemented a python script using \texttt{matplotlib} that reads the result file and display the 3D plots.

\begin{figure}
\begin{tt}
wator-cli>ls \\
wator-cli>select predator Shark\\
wator-cli>select prey Fish\\
wator-cli>set Shark population 10\\
wator-cli>set Fish population 20\\
wator-cli>set Shark strategy Random(5)\\
wator-cli>set Fish strategy InertiaRandom(5,7,3,3)\\
wator-cli>start 1 10 1 10 1 10 1 1 1 \\
Number of rounds ?> 400\\
Number of simulations ?> 5\\
Output file prefix ?> mas-report-output\\
\end{tt}
\caption{The usage example of the Wa-Tor comand-line interface.}
\label{wator:cli}
\end{figure}

\section{Movement Strategies}
\label{sec:strategies}
As already mentioned, each agent has to decide where it will move to in the next step. Agents base their descisions on different movement strategies. The output of a movement strategy is a vector (2D or 3D respectivly), which is than added to the current agent position. Note that in our implementation, all agents of a distinct species share the same movement strategy. We implemented following strategies: random, inertia-random and force vector movement strategy. In this section, we discuss each of them in depth. Parameters of all movement strategies are summed up in Figure~\ref{fig:strategiesParam}.

\begin{figure}[htb]
	\begin{itemize}
		\item \textbf{Random Movement Strategy}
			\begin{itemize}
				\item \textit{Reach}: the length of the movement vector
			\end{itemize}
		\item \textbf{Inertia-Random Movement Strategy}
			\begin{itemize}
				\item \textit{Reach}: the length of the movement vector
				\item \textit{Inertia weight}: the $\alpha$ value of the weighted sum
				\item \textit{Maximal velocity}: the maximal length of the movement vector
			\end{itemize}
		\item \textbf{Force Vector Movement Strategy}
			\begin{itemize}
				\item \textit{Inertia}: Inertia weight (importance of previous direction vector)
				\item \textit{Flocking}: flocking weight
				\item \textit{Separation Range}: Minimal distance between individuals in a flock
				\item \textit{Prey attraction}: weight for prey attraction
				\item \textit{Energy attraction}: weight for energy attraction
				\item \textit{Predator avoidance}: weight for predator avoidance
				\item \textit{Maximal velocity}: maximal length of direction vector
			\end{itemize}
	\end{itemize}
	\caption{Parameters of all movement strategies with short descriptions.}
	\label{fig:strategiesParam}
\end{figure}

\subsection{Random Movement Strategy}
The simpliest movement strategy generates a random vector and does not take its neighbourhood into account. Its only parameter (\textit{reach}) specifies the maximum length of the new direction vector.

\subsection{Inertia Movement Strategy}
\label{subsec:inertiaMS}
This movement strategy approximates real world moving behaviors more closely than the previous strategy. The old direction vector is taken into account in order to prevent the agent of sudden movements and changes of its direction, e.g.\ moving one step forward, and right after moving to the exact previous position. Therefore, the direction vector for iteration $i$ is the following weighted sum
\[ v_i=\alpha \cdot v_{i-1}+(1-\alpha) \cdot v_{random}\]
where $v_{random}$ represents a randomly chosen direction vector, $v_{i-1}$ direction vector from previous step. $\alpha$ is defined by the user as a parameter of this movement strategy. Since the direction vector is calculated as the sum of two vectors, it could easily exceed the limit set by the reach paramter. In that case, we shrink the direction vector to the length of \textit{maximal velocity}.

\subsubsection{Inertia-Random On Speed Movement Strategy}
This movement strategy uses the same approach as Inertia-Random, but assures that the direction vector always exactly have the length \textit{maximal velocity}.

\subsection{Force Vector Movement Strategy}
\begin{figure*}[thb]
	\begin{minipage}[b]{0.3\linewidth}
		\centering
		\centerline{\includegraphics[width=3.0cm]{Cohesion.png}}
		\centerline{Cohesion}\medskip
	\end{minipage}
	\begin{minipage}[b]{0.3\linewidth}
		\centering
		\centerline{\includegraphics[width=3.0cm]{Separation.png}}
		\centerline{Separation}\medskip		
	\end{minipage}		
	\begin{minipage}[b]{.3\linewidth}
		\centering
		\centerline{\includegraphics[width=3cm]{Alignment.png}}
		\centerline{Alignment}\medskip
	\end{minipage}
	\caption{Three rules for implementing flocking without direct communication.}
	\label{fig:flocking}
\end{figure*}

This movement strategy combines five different strategies. Each of them define a sub direction vector in each round. We can think of this approach as a combination of different forces, which draws the agent in different directions. The final direction vector is calculated as the weighted sum

\[v = \sum_{n \in M_s} \alpha_n \cdot v_n \]
\[M_s = \lbrace inertia, preyAtt, energyAtt, predatorAvoid, flock \rbrace\]

The weights $\alpha_n$ are of course configurable by the user as strategy parameters (see Figure~\ref{fig:strategiesParam}). We describe each element of this sum in the following subsections. Note that all of the strategies described in the subsections \ref{subsubsec:FV_preyAtt}-\ref{subsubsec:FV_flock} heavily rely on the structure of the neighbourhood.

\subsubsection{Inertia}
Calculates the direction vector as described in subsection~\ref{subsec:inertiaMS}.

\subsubsection{Prey Attraction}
\label{subsubsec:FV_preyAtt}
This strategy facilitates controlled hunting behaviour for predators. Each prey in the neighbourhood of the hunter induces a force drawing it in this direction. The final direction vector is the sum of all those force vectors. In other words, predators using this strategy are rather moving towards a fish flock than a single fish on other side, even if the single fish is nearer.

\subsubsection{Energy Attraction}
\label{subsubsec:FV_energyAtt}
This is a more general case of \ref{subsubsec:FV_preyAtt}. If the Wa-Tor world consists only of sharks and fishes, this strategy will be exactly the same as \textit{prey attraction}. However, if we have fishes of different sizes, the big fishes have more weight in the final direction vector of the predator (proportional to its \textit{engery values}): 
\[ v = \sum_{n} \alpha_{n} \cdot v_n \],
where $n$ iterates over the prey in the neighborhood of the predator, and $\alpha_{n}$ represents the "energy value" of the $n$-th prey. For instance $\alpha_{n} = 5$ for big and $\alpha_{n} = 1$ for small fishes.

\subsubsection{Predator Avoidance}
\label{subsubsec:FV_predAvoid}
Predator avoidance strategy makes prey run away from the predators. Each predator in the neighborhood of the prey is taken into account and the final direction vector of the prey is calculated as 
\[ v = -1 \cdot \sum_{n} v_{n}\]
with $n$ iterates through the predators in the neighborhood, and $v_n$ is the vector directing to the predator from the prey. Changing the sign of the sum reults in a force, which draws the prey away from the predators.

\subsubsection{Flocking}
\label{subsubsec:FV_flock}
Flocking is a well-known phenomenon in the nature. Preys often move together in big flocks or schools in order to enhance their evolutionary performance. The author in \cite{flocks:herds} proposes three different rules to implement flocking, which are illustrated in Figure~\ref{fig:flocking}. The outer circle represents the neighbourhood, the size of the inner circle is defined by the seperation radius (strategy parameter).

The individuals in a flog have to keep a certain distance to each other in order to avoid collisions. Thus, the \textbf{cohesion} rule takes care that each individual of the flock keeps its neighbours near but no nearer than set seperation range (see Figure~\ref{fig:strategiesParam}).

The \textbf{Seperation} rule makes individuals turn away from obstacles or enemys. As soon as the obstacle is noticed, the direction vector is calculated so it aims away from it. If there is more than one obstacle, we determine the direction vector similar as in \ref{subsubsec:FV_predAvoid}. Additionally, we weight the sum so that the nearer the obstacle is, the bigger is the repel effect.

Since flocks can grow very big, it often happens that not all individuals can see the obstacle or enemy on their path. However, the alignment \textbf{alignment} rule enables the flock to show signs of collective intelligence, because even if individuals do not yet see the predator, they tend to avoid because this information is implicitly delivered among flock members by their direction vector. Therefore, it changes the direction of each individual in the flock according to the direction of other individuals in its neighbourhood.

\section{Experiments and results}

Section \ref{wator:cli} described two different kinds of diagrams we used for analytic proposes. In the first kind of diagrams, we plot population sizes over time. The second group of experiments abstracts from the time component, and show results in the species parameter space.

\subsection{Time dependent analysis}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.99\linewidth]{random-random.png}
	\caption{High frequency fluctuations of population sizes.}
	\label{fig:random-random}
\end{figure}

Figure~\ref{fig:random-random} show a typical simulation plot, when both species use random movement strategies. Very striking here are the high frequency oscilations in both population sizes. This effect can be observed in the nature, and is also described by the Lotka-Volterra equation \cite{lotka}: a large number of preys are the basis of good living conditions and numerous reproduction of predator individuals, which eat more prey. As predators outnumber the preys, there is not enough food anymore and predator begin to starve. A reduced number of predators then leads again to a increased number of preys. We summarize this observation in our first result.

\begin{quotation}
1.) In our simulation enviroment, equlibriums are possible, in which the population sizes oscilate, but none of the species are removed completely from the world. Such patterns are common in real-world predator-prey relationships.
\end{quotation}

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.99\linewidth]{longterm.png}
	\caption{High and low frequency fluctuations in predator-prey population dynamics.}
	\label{fig:longterm}
\end{figure}

Both populations show the same periodical patterns, the predators slightly time-shifted. A longer simulation is plotted in Figure~\ref{fig:longterm}. Here, the high frequency oscilations from Figure~\ref{fig:fick} are underlied by very low frequency fluctuations. The number of preys seem to dictate the number of predators again -- if the average prey population size goes up, the number of predaors follow slowly. However, the amplitudes of low frequency oscilations are much higher for the prey population. We can sum up the observations so far in our second result:

\begin{quotation}
2.) The population size of the predators follows the number of preys. We observe the same patterns in high frequency oscilations, as well as in longer-term population dynamics.
\end{quotation}

Even if this simulation shows a large number of rounds, the ecosystem is not stable. At the end, all the fishes are eaten, and as consequence all the sharks starve shortly after.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.99\linewidth]{shark-flock.png}
	\caption{Sharks hunting in flocks.}
	\label{fig:shark-flock}
\end{figure}

A major result of the next section is, that the predators perform worse if they hunt in flocks. Figure~\ref{fig:shark-flock} suggests a possible explanation of this result. The fishes in this diagram move according a random movement strategy, while the sharks use the force vector strategy and flock. Indications of the high frequency oscilations of the previous experiments can be observed again. However, they do not result in periodic patterns, as the fishes born in one breed interval are not eaten by the sharks. The reason is, that the sharks build flocks, so they can not cover the world sufficiently to reach all fishes. But this would not be a problem, if the shark flock would grow bigger and bigger, finally covering the whole world. However, the shark population stays very low, because only the sharks at the head of the flock gets food, while the tail of the flocks starves as others take all the prey. This observation will be our third result.

\begin{quotation}
3.) Predators hunting in a flock perform worse as when they move randomly. More sophisticated flocking strategy, in which the head of the flock alternates in a round-robin like pattern, or in which flocks are kept small, are likely to outperform random movements though.
\end{quotation}

\subsection{Parameter space analysis}

In Figure~\ref{fig:fick}, the strategy of the fishes are fixed to the force vector strategy, while the shark strategy switches between our three implementation random, inertia-random, and force vector. The third result stated above is now more obvious. In fact, sharks did not win at all when they used flocking. The diagrams in Figure~\ref{fig:fick} lead us to our last result, that is about the circumstances in which equilibriums are possible.

\begin{quotation}
4.) The more similar the strategies of predator and prey are, the more likely are equlibriums between them.
\end{quotation}

\section{Conclusion and Future work}

\bibliographystyle{abbrv}
\bibliography{wator}  

\appendix
%Appendix A
\section{Wa-Tor screenshots}
\label{app:GUI}
\begin{figure*}
	\centering
	\includegraphics[width=15.0cm]{flocks.png}
\end{figure*}

\begin{figure*}
	\centering
	\includegraphics[width=15.0cm]{WaTor.png}
\end{figure*}

\end{document}
